package com.example.leetcode.prcatice;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的子序列的单词个数 。
 *
 * 字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。
 *
 * 例如， “ace” 是 “abcde” 的子序列。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-matching-subsequences
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test792 {


    public int numMatchingSubseq(String s, String[] words) {
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0;i<s.length();i++) {
            List<Integer> orDefault = map.getOrDefault(s.charAt(i), new ArrayList<>());
            orDefault.add(i);
            map.put(s.charAt(i),orDefault);
        }
        int r = 0;
        for (String s1:words) {
            int len = s1.length();
            boolean add = true;
            int idx = -1;
            for (int i = 0;i<len && add;i++) {
                List<Integer> orDefault = map.getOrDefault(s1.charAt(i), new ArrayList<>());
                int left = 0;
                int right = orDefault.size() -1;
                while (left < right) {
                    int mid = left + right >> 1;
                    if (orDefault.get(mid) > idx) {
                        right = mid;
                    }else {
                        left = mid +1;
                    }
                }
                if (right < 0 || orDefault.get(right) <= idx) {
                    add = false;
                } else {
                    idx = orDefault.get(right);
                }
            }
            if (add) {
                r++;
            }
        }
        return r;
    }
}
